package review.Day_0411;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zxc
 * @date 2023/04/11 22:18
 **/
public class Solution02 {
    // 迭代实现二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                result.add(root.val);
                root = root.leftNode;
            }
            // 所维护的栈stack中元素被弹出时，代表该树节点的左子树已经被完全遍历;
            root = stack.pop();
            root = root.rightNode;
        }
        return result;
    }

    // 迭代实现二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.leftNode;
            }
            // 所维护的栈stack中元素被弹出时，代表该树节点的左子树已经被完全遍历;
            root = stack.pop();
            result.add(root.val); // 中序遍历时，根节点加入结果集合的时机，在于当前根节点的左子树被遍历完
            root = root.rightNode;
        }
        return result;
    }

    // 迭代实现二叉树的后序遍历
    // 需要注意的是，二叉树的后序遍历和前序遍历/中序遍历是有很大不同的;
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // 维护树节点prev，来判断当前根节点的右子树是否被遍历完;
        // 栈中元素首次被拿取时，代表该元素的左子树是被完全遍历过的，但是后序遍历需要在遍历完该元素的右子树后，再将该元素加入到结果集合中;
        TreeNode prev = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.leftNode;
            }
            root = stack.pop();
            // （1）root.rightNode == null : 当前根节点的右子树不存在;
            // （2）root.rightNode == prev : 当前根节点的右子树被完全遍历;
            if(root.rightNode == null || root.rightNode == prev){
                result.add(root.val); // 后序遍历插入时机，在于根元素的左右子树都被遍历完;
                // 变量prev，用于后续遍历节点去判断其右子树是否已经被遍历完;
                prev = root;
                root = null;
            }
            else {
                stack.push(root);
                root = root.rightNode;
            }
        }
        return result;
    }

}
